package com.example.leetdemo.process;

public class Solution209 {

    public int minSubArrayLen(int target, int[] nums) {
        int[] dp = new int[nums.length + 1];
        int k = nums.length;
        for (int i = 0; i < nums.length; i++) {
            dp[i + 1] = dp[i] + nums[i];
            if (nums[i] >= target) {
                return 1;
            }
            if (dp[i + 1] >= target) {
                k = subLength(0, i + 1, k, dp, target);
            }
        }
        if (dp[nums.length] < target) {
            return 0;
        }
        return k;
    }

    private int subLength(int p, int q, int k, int[] dp, int target) {
        int m = (q - p) / 2 + p;
        while (m != p) {
            if (dp[q] - dp[m] >= target) {
                p = m;
                m = (q - p) / 2 + p;
            } else {
                m = (m - p) / 2 + p;
            }
        }
        return Math.min(k, q - p);
    }

    public static void main(String[] args) {
        Solution209 solution209 = new Solution209();
        System.err.println(solution209.minSubArrayLen(213, new int[] {12,28,83,4,25,26,25,2,25,25,25,12}));
    }

}
